'''
树状数组，
单点插入
区间查询
'''

class IndexTree():
    def __init__(self, size = 32):
        self.tree = [0] * (size + 1)
        self.N = size

    def add(self, i, v):
        while i <= self.N:
            self.tree[i] += v
            i += i & -i

    def _sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def sum(self, l, r):
        return self._sum(r) - self._sum(l - 1)